The integrity of data stored in storage systems is typically protected by error detection or correction code methods. Shown in FIG. 1 is a block diagram of a small computer system interface (SCSI) controller 100. Data is received from a SCSI bus 105 and provided through the blocks shown to a buffer manager 110. Data flow is controlled by buffer manager 110, and data is provided to a disk FIFO 120 and an Error Correction Coding (ECC) engine 130. ECC engine 130 encodes the received data with a generator polynomial g(x). In this manner ECC bytes are created and are transmitted to a disk formatter 140 concurrently with the data from disk FIFO 120. The ECC bytes are appended to the data by disk formatter 140 and then provided to a storage device, such as a hard drive (not shown), which is coupled to lead 145. The hard drive typically stores the data in 512 byte sectors with the multiple ECC bytes appended at the end.
The data sector is read from the drive and interleaved, usually a 3-way interleave. 3-way interleave is typical due to constraints on how many bytes the ECC logic can decode, i.e., the ECC logic cannot decode the entire sector. To this end, the ECC bytes usually contain an ECC byte for each interleave. For example, the following data sector ##STR1## is 3-way interleaved as ##STR2## where each row represents an interleave and the number of columns equals n/3.
For a read operation, disk formatter 140 receives the interleaved sector as a plurality of code words. Each code word can be represented as a polynomial c(x). Thus, the data bytes that form the code words of each interleave can be represented as a polynomial defined as v(x)=c(x)+e(x), where e(x) is an error polynomial that represents at most t errors in the stored data. From the received polynomial v(x), partial syndromes can be defined. The partial syndromes, in turn, are used to compute the coefficients of an error-locator polynomial .LAMBDA.(x). The partial syndromes and the coefficients of the error-locator polynomial determine the error-locator polynomial. Next, the error value or magnitude is determined for each error location. Finally, the error is corrected. A more detailed discussion of the above can be obtained from Weldon, E. J., "Error Correcting Codes with Application to Digital Storage Systems," Seminar Notes, University Consortium for Continuing Education (May 1993), which is incorporated herein by reference.
To illustrate, an interleaved 3-burst Reed Solomon code has an error-locator polynomial defined to be: EQU .LAMBDA.(x)=.LAMBDA..sub.3 x.sup.3 +.LAMBDA..sub.2 x.sup.2 +.LAMBDA..sub.1 x+1 (1).
.LAMBDA..sub.3, .LAMBDA..sub.2 and .LAMBDA..sub.1, are 8-bit symbols or field elements in Galois Field GF(2.sup.8). A Galois Field GF(2.sup.m) is a distinct set of 2.sup.m -1 m-bit symbols of .alpha..sup.i where i is an integer ranging from 0 to 2.sup.m -2, and can be used to index or locate the ith m-bit symbol within an encoded interleaved message or sector. The logarithms of the implicative inverse of the roots (log.sub.2 (.alpha..sup.-i)) of this error-locator polynomial are the error offsets or locations of the interleaved sector with 0 being the farthest encoded ECC byte. Since for an 8-bit GF(2.sup.8) there are only 255 field elements to check, the simplest way to find the zeros or roots of the error-locator polynomial .LAMBDA.(x) is by trial and error, a process known as a Chien search. .LAMBDA.(.alpha..sup.-i) is computed for each i and checked for zero. In other words, EQU .LAMBDA.(.alpha..sup.31 i)=.LAMBDA..sub.3 x.sup.3 +.LAMBDA..sub.2 x.sup.2 +.LAMBDA..sub.1 x+1.vertline..sub.x=.alpha..sup.-i =0 (2).
Executing Equation 2 for each i requires four multipliers (about 300 gates each), two squaring circuits (about 50 gates each), on 4-input adder (8-bitwise 4-input exclusive-OR) and a logarithm circuit of the inverse of i to produce .alpha..sup.-i in GF(2.sup.8). For a n-way interleaved Chien search in parallel, the gate count could run up to 4n multipliers, 2n squaring circuits and a logarithm circuit. Besides, the critical path for this type of execution which goes through a squaring circuit (about 2 ns), two multipliers (about 12 ns) and an adder (about 2 ns) requires roughly 30 ns. Consequently, this logic is restricted to around a 33 MHz 8-bit NRZ clock speed.
In addition to data errors occurring randomly in digit positions of v(x), some disturbances in the data path may corrupt an entire block of digits. For example, platter defects of hard disk drives usually affect more than one digit. A burst error is an error that occurs over a sequence of b digits of a data block. For a burst error sequence, the first and bth digits are in error, while the intermediate digits may or may not be in error. A burst error can extend over the interleaves. An error correction code implemented as an L-way interleave with a burst-correcting capability of M provides a code that has a burst-correcting capability of LM.
A burst-correction capability of an ECC can be limited to improve (decrease) the probability of miscorrection. Some hard disk controller ECCs have burst limiting logic that operates after all the error patterns are identified. Such configuration involves sorting all error locations numerically to determine subsequent burst spans. As a result, additional hardware overhead is imposed and on-the-fly performance will degrade.
A need exists for an ECC device that includes a high-speed Chien Search circuit that requires less logic, thereby reducing design cost, complexity and physical area requirements. A further need exists for an ECC device that has burst-limiting capability which minimizes on-the-fly performance degradation, hardware overhead and associated costs. The present invention meets these needs.